#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// 荷兰国旗问题的单向版本
vector<int> helan(vector<int> &nums, int target) {
  int pointsmall = -1;
  int pointeq = -1;
  int point = 0;
  while (point < nums.size()) {
    if (nums[point] < target) {
      swap(nums[pointeq + 1], nums[pointsmall + 1]); // 先换出来
      ++pointeq;
      swap(nums[point], nums[pointsmall + 1]); // 再换进去
      ++pointsmall;
    } else if (nums[point] == target) {
      swap(nums[pointeq + 1], nums[point]);
      ++pointeq;
    }
    ++point;
  }
  return {pointsmall + 1, pointeq};
}

// 双向target指定版本
vector<int> helan2(vector<int> &nums, int l, int r, int target) {
  if (l > r) {
    return {-1, -1};
  }

  if (l == r) {
    return {l, r};
  }

  int pointsmall = l - 1;
  int pointmore = r + 1;
  int point = l;
  while (point < pointmore) {
    if (nums[point] < target) {
      swap(nums[point], nums[pointsmall + 1]);
      ++pointsmall;
      ++point;
    } else if (nums[point] == target) {
      ++point;
    } else {
      swap(nums[point], nums[pointmore - 1]);
      --pointmore;
    }
  }
  return {pointsmall + 1, pointmore - 1};
}

// 以r为轴的版本
vector<int> helan3(vector<int> &nums, int l, int r) {
  if (l > r) {
    return {-1, -1};
  }

  if (l == r) {
    return {l, r};
  }

  int pointsmall = l - 1;
  int pointmore = r;
  int point = l;
  int target = nums[r];
  while (point < pointmore) {
    if (nums[point] < target) {
      swap(nums[point], nums[pointsmall + 1]);
      ++pointsmall;
      ++point;
    } else if (nums[point] == target) {
      ++point;
    } else {
      swap(nums[point], nums[pointmore - 1]);
      --pointmore;
    }
  }
  swap(nums[pointmore], nums[r]);
  return {pointsmall + 1, pointmore};
}

//++优化版本
vector<int> helan4(vector<int> &nums, int l, int r) {
  if (l > r) {
    return {-1, -1};
  }

  if (l == r) {
    return {l, r};
  }

  int pointsmall = l - 1;
  int pointmore = r;
  int point = l;
  int target = nums[r];
  while (point < pointmore) {
    if (nums[point] < target) {
      swap(nums[point++], nums[++pointsmall]);
    } else if (nums[point] == target) {
      ++point;
    } else {
      swap(nums[point], nums[--pointmore]);
    }
  }
  swap(nums[pointmore], nums[r]);
  return {pointsmall + 1, pointmore};
}

int main() {
  vector<int> a = {3, 4, 6, 0, 7, 4, 5, 1, 3};
  helan4(a, 0,a.size()-1);
  for (auto p = a.begin(); p != a.end(); ++p) {
    cout << *p << " ";
  }
  cout << endl;
}
